import { measureSort, swap, testSort } from "hy-algokit";

// 从一个数列中的第二个值开始，与前面的值比较，如果前面的值比较自己大，则将前面的牌的后面的值整体右移动，拆入当前牌
// 新值，插入到前面有序的位置

//这是我自己用双重for循环整出来的,这个好像不对，我这样写好像是冒泡排序的逻辑，不知道是啥，也排出来了
// function interSort(arr: number[]):number[] {
//     let n = arr.length;
//     for(let i = 0;i < n ; i++){
//         let firstIndex = i;
//         for(let j = firstIndex + 1; j < n; j++) {
//             if(arr[j] < arr[firstIndex]) {
//                 swap(arr,j,firstIndex)
//             }
//         }
//     }

//     return arr;
// }

// 内部循环用while
export default function insertionSort(arr: number[]):number[] {
    let n = arr.length;
    // 从第二值，开始和前面的值比
    for(let i = 1;i < n ; i++){
        let newNum = arr[i];
        let j = i - 1;
        // 内层循环用while，是因为当前位置不确定要插入多少从，对于次数不确定的，用while循环比较好
        // 当前面的值比其大时，将
        while(arr[j] > newNum && j >= 0) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j + 1] = newNum;
    }

    return arr;
}

testSort(insertionSort);
measureSort(insertionSort);
